# 排序算法
###1.直接插入排序，按升序排
lst = [1, 7, 2, 3, 8, 4]
lst1=[15,26,17,36,54,8,3,12]
def zhijiecharu(lst):
    for i in range(len(lst)):
        enum=lst[i]
        for j in range(len(lst[0:i])):
            if lst[i] < lst[j]:
                lst[j+1:i+1]=lst[j:i]
                lst[j]=enum
                break
    return lst
# print("直接插入排序的结果为：",zhijiecharu(lst1))


###2.直接选择排序，按升序排
def choice_sort(lst):
    for i in range(len(lst)):
        max1=max(lst[i:])
        temp=lst[i]
        lst[i]=max
        ind=lst.index(max)
        lst[ind]=temp
    return lst
# print("直接选择排序的结果为：",choice_sort(lst1))

##百度
# 3.希尔排序
def shell_sort(list):
    n = len(list)
    # 初始步长
    gap = n // 2   #每次分组的长度
    while gap > 0:
        for i in range(gap, n):
            # 每个步长进行插入排序
            temp = list[i]
            j = i
            # 插入排序
            while j >= gap and list[j - gap] > temp:
                list[j] = list[j - gap]
                j -= gap
            list[j] = temp
        # 得到新的步长
        gap = gap // 2
lst = [1, 7, 2, 3, 8, 4,5,6,12,34]
# shell_sort(lst)
# print(lst)

# 4.冒泡排序
def maopao(lst):
    for i in range(0,len(lst)-1):   #比较趟数，需要比较n-1,
        max=lst[0];
        for j in range(1,len(lst)-i):  #每趟比较次数，n-1次
            if max>lst[j]:
                lst[j-1],lst[j]=lst[j],lst[j-1]  #进行互换
            max = lst[j];
    return lst
# print(maopao(lst))

# 5.快速排序
def kuaipai(list, left, right):
    if left >= right:  #判断下标值
        return list
    jz = list[left]# 将左边第一位定位基准数，以此数将序列分为两部分
    min = left  #开始进行搜索
    max = right
    while left != right:
        while left < right :# 从最右边开始查，找到第一个比基准值小的数
            if list[right] >= jz:
                right -= 1
            else:# 从最左边开始查，查找比基准值大的数
                list[left] = list[right]
                left += 1
                list[right] = list[left]
        list[right] = jz
    #递归调用
    kuaipai(list, min, left - 1)
    kuaipai(list, left + 1, max)
    return list
lst=[13451,24,1234,23,34,43,23]
# print(kuaipai(lst,0,len(lst)-1))